Skip to content

Latest commit

 

History

History

0599-Minimum Index Sum of Two Lists

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
Brute Force.rs
Brute Force.rs
 
 
HashMap.rs
HashMap.rs
 
 
Increasing Sum.rs
Increasing Sum.rs
 
 
README.md
README.md
 
 
README_CN.md
README_CN.md
 
 

README.md

599. Minimum Index Sum of Two Lists

Suppose Andy and Doris want to choose a restaurant for dinner, and they both have a list of favorite restaurants represented by strings.

You need to help them find out their common interest with the least list index sum. If there is a choice tie between answers, output all of them with no order requirement. You could assume there always exists an answer.

Example 1:

Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"] Output: ["Shogun"] Explanation: The only restaurant they both like is "Shogun".

Example 2:

Input: ["Shogun", "Tapioca Express", "Burger King", "KFC"] ["KFC", "Shogun", "Burger King"] Output: ["Shogun"] Explanation: The restaurant they both like and have the least index sum is "Shogun" with index sum 1 (0+1).

Note:

  1. The length of both lists will be in the range of [1, 1000].
  2. The length of strings in both lists will be in the range of [1, 30].
  3. The index is starting from 0 to the list length minus 1.
  4. No duplicates in both lists.

Solutions (Rust)

1. Brute Force

implSolution{pubfnfind_restaurant(list1:Vec<String>,list2:Vec<String>) -> Vec<String>{letmut min_sum = std::usize::MAX;letmut ret = Vec::new();for i in0..list1.len(){for j in0..list2.len(){if list1[i] == list2[j]{if i + j == min_sum { ret.push(list2[j].to_string());}elseif i + j < min_sum { ret.clear(); ret.push(list2[j].to_string()); min_sum = i + j;}break;}}} ret }}

2. HashMap

use std::collections::HashMap;implSolution{pubfnfind_restaurant(list1:Vec<String>,list2:Vec<String>) -> Vec<String>{letmut rest_idx = list1 .iter().enumerate().map(|(i, s)| (s, i)).collect::<HashMap<&String,usize>>();letmut min_sum = std::usize::MAX;letmut ret = Vec::new();for i in0..list2.len(){ifletSome(j) = rest_idx.get(&list2[i]){if i + j == min_sum { ret.push(list2[i].to_string());}elseif i + j < min_sum { ret.clear(); ret.push(list2[i].to_string()); min_sum = i + j;}}} ret }}

3. Increasing Sum

implSolution{pubfnfind_restaurant(list1:Vec<String>,list2:Vec<String>) -> Vec<String>{letmut flag = false;letmut ret = Vec::new();for sum in0..(list1.len() + list2.len() - 1){for i in(sum + 1).saturating_sub(list2.len())..(sum + 1).min(list1.len()){if list1[i] == list2[sum - i]{ flag = true; ret.push(list1[i].to_string());}}if flag {break;}} ret }}
close